import { Vec2, Rect, Segment, Line2, Parallelogram } from "./geometry";
import { Mat3 } from "./matrix";
/**
 * 最小覆盖矩形实现
 * @date 2023/12/4 - 15:18:54
 *
 * @param {Vec2[]} convex 输入凸包
 * @returns {{}}
 */
export function minimalCoverRect(convex: Vec2[]) {
  if (convex.length === 0) {
    return [];
  }

  let minArea = Infinity;
  let minMat: Mat3 = new Mat3();
  let minRect: Rect = new Rect();
  for (let i = 0; i < convex.length - 1; i++) {
    let xv = convex[i + 1].sub(convex[i]).normalize();
    let yv = xv.prep();
    let mat = Mat3.makeFromBasis(xv, yv);
    let rmat = mat.transpos();

    let rect = new Rect();
    for (const p of convex) {
      let np = rmat.applyToVec(p);
      rect.expandPoint(np);
    }
    let area = rect.area;
    if (area < minArea) {
      minMat = mat;
      minRect = rect;
      minArea = area;
    }
    console.log(area);
  }
  console.log(`min area is ${minArea}`);

  let rectPoints: Vec2[] = [];
  rectPoints.push(minMat.applyToVec(minRect.bl));
  rectPoints.push(minMat.applyToVec(minRect.br));
  rectPoints.push(minMat.applyToVec(minRect.tr));
  rectPoints.push(minMat.applyToVec(minRect.tl));
  return rectPoints;
}

/**
 * 最小覆盖平行四边形
 * @date 2023/12/4 - 18:33:24
 *
 * @param {Vec2[]} convex
 * @returns {*}
 */
export function minimalCoverParallelogram(convex: Vec2[]) {
  let minParagram;
  let minArea = Infinity;
  let pairs = getEdgeVertexPairs(convex);
  let j = 1;
  for (let i = 0; i < pairs.length; i++) {
    let z1 = pairs[i];
    let z2 = pairs[j];
    while (true) {
      z2 = pairs[j];
      let v = z2.edge.p2.sub(z2.vertex);
      if (!Vec2.turnLeft(v, z1.edge.vec)) {
        break;
      }

      j = (j + 1) % pairs.length;
      if (j == i) {
        j = (j + 1) % pairs.length;
      }
    }

    // p与z2在z1向量方向有交集
    if (!Vec2.turnRight(z2.edge.p1.sub(z2.vertex), z1.edge.vec)) {
      let paragram = getParagram(z1, z2);
      let area = paragram.area;
      console.log(`area is ${area}`);

      if (area < minArea) {
        minArea = area;
        minParagram = paragram;
      }
    }

    if (!Vec2.turnRight(z2.edge.p2.sub(z2.vertex), z1.edge.vec)) {
      j = (j + 1) % pairs.length;
      z2 = pairs[j];
      let paragram = getParagram(z1, z2);
      let area = paragram.area;
      console.log(`move to next area ${area}`);
      if (area < minArea) {
        minArea = area;
        minParagram = paragram;
      }
    }
  }

  return minParagram;
}

/**
 * 根据两对足对获取平行四边形
 * @date 2023/12/4 - 19:38:39
 *
 * @param {EdgeVertexPair} z1
 * @param {EdgeVertexPair} z2
 * @returns {Parallelogram}
 */
function getParagram(z1: EdgeVertexPair, z2: EdgeVertexPair) {
  let l1 = Line2.from2Points(z1.edge.p1, z1.edge.p2);
  let l2 = Line2.from2Points(z2.edge.p1, z2.edge.p2);
  let l3 = new Line2(z1.vertex, z1.edge.vec);
  let l4 = new Line2(z2.vertex, z2.edge.vec);
  let a = Line2.intersect(l1, l2);
  let b = Line2.intersect(l2, l3);
  let c = Line2.intersect(l3, l4);
  return new Parallelogram(a, b, c);
}

/**
 * 计算所有对足对
 * @date 2023/12/4 - 19:37:50
 *
 * @param {Vec2[]} convex
 * @returns {{}}
 */
function getEdgeVertexPairs(convex: Vec2[]) {
  let pairs: EdgeVertexPair[] = [];
  for (let i = 0, j = 1; i < convex.length - 1; i++) {
    const v = convex[i + 1].sub(convex[i]);
    while (true) {
      let k = (j + 1) % (convex.length - 1);
      if (!Vec2.turnRight(convex[k].sub(convex[j]), v)) {
        pairs.push(new EdgeVertexPair(convex[i], convex[i + 1], convex[j]));
        break;
      }
      j = k;
    }
  }
  return pairs;
}

/**
 * 对足对
 * @date 2023/12/4 - 15:50:30
 *
 * @class EdgeVertexPair
 * @typedef {EdgeVertexPair}
 */
class EdgeVertexPair {
  edge: Segment;
  vertex: Vec2;

  constructor(begin: Vec2, end: Vec2, vertex: Vec2) {
    this.edge = new Segment(begin, end);
    this.vertex = vertex;
  }

  get width() {
    return Math.abs(this.vertex.sub(this.edge.p1).cross(this.edge.vec.normal));
  }
}
